package com.mdnote.jianzhi_offer.recursion;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/18
 * @description 剑指 Offer 16. 数值的整数次方
 */
public class Offer16 {

    public static void main(String[] args) {
        Offer16 offer16 = new Offer16();
        double v = offer16.myPow(2.0, Integer.MIN_VALUE);
        System.out.println(v);

    }

    public double myPow(double x, int n) {
        // basse case
        if (x == 0) {
            return 0;
        }
        if (n == 0 || x == 1) {
            return 1;
        }

        long n_long = n;
        // negative
        if (n_long < 0) {
            x = 1 / x;
            n_long = -n_long;
        }

        return _pow(x, n_long);
    }

    private double _pow(double x, long n) {

        // Terminator
        if (n == 1) {
            return x;
        }

        double res = _pow(x, n >> 1);
        if ((n & 1) == 0) {
            return res * res;
        } else {
            return res * res * x;
        }
    }
}
